/*
 public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}
*/
import java.util.*;

public class Solution {
    public ListNode cycle(ListNode pHead) {
        ListNode fast = pHead, slow = pHead;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
            if (slow == fast) {
                return fast;
            }
        }
        return null;
    }

    public ListNode EntryNodeOfLoop(ListNode pHead) {
        //
        /*
        Set<ListNode> set = new HashSet<>();
        ListNode dummy = pHead;
        while (dummy != null) {
            if (set.contains(dummy)) {
                return dummy;
            }
            else {
                set.add(dummy);
                dummy = dummy.next;
            }
        }
        return dummy;
        */

        // 双指针  算数推导 -> 步数规律
        ListNode slow = cycle(pHead);
        if (slow == null) {
            return null;
        }
        ListNode fast = pHead;
        while (fast != slow) {
            fast = fast.next;
            slow = slow.next;
        }
        return fast;
    }
}
